岛屿数量(Leetcode 200)

发表于 | 分类于 ， ， ， | | 本文总阅读数 次
| 字数统计: 1k | 阅读时长 ≈ 4
Leetcode 200

1

题目分析

   岛屿数量问题是一个经典的问题，与朋友圈问题(Leetcode 547)类似，只不过朋友圈问题中的矩阵是对称的，而岛屿数量中的矩阵是非对称的。此题可以使用DFS，BFS和并查集进行求解。

DFS

DFS是先找到一块岛屿，然后对这个岛屿进行深度优先搜索，已知沿着某一个路径走下去，如果没用路可以走则回溯。直到所有的路径都走完，说明将这个岛屿探索完毕，将其剔除，从剩余的地图上继续寻找，直到所有的岛屿都找到，则算法结束，有关DFS的知识可以参考我的另一篇博客深度优先搜索(Depth-First-Search)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution:
    def numIslands(self, grid):
        row = len(grid)
        if row == 0:
            return 0
        col = len(grid[0])

        def dfs(x, y):
            grid[x][y] = 0
            for new_x, new_y in [(x - 1, y), (x + 1, y), (x, y - 1), (x, y + 1)]:
                if 0 <= new_x < row and 0 <= new_y < col and grid[new_x][new_y] == '1':
                    dfs(new_x, new_y)

        num_islands = 0
        for r in range(row):
            for c in range(col):
                if grid[r][c] == "1":
                    num_islands += 1
                    dfs(r, c)
        return num_islands

BFS

BFS是先找到一块岛屿，然后对这个岛屿进行广度优先搜索，以某个点为中心，先寻找距离该点为1的所有陆地，然后再寻找与该点距离为2的所有陆地，依次进性，直到将与该点连通的所有陆地都寻找完毕，说明将这个岛屿探索完毕，将其剔除，从剩余的地图上继续寻找，直到所有的岛屿都找到，则算法结束，有关BFS的知识可以参考我的另一篇博客广度优先搜索(Breadth-First-Search)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
from collections import deque


class Solution:
    def numIslands(self, grid):
        row = len(grid)
        if row == 0:
            return 0
        col = len(grid[0])

        num_islands = 0
        for r in range(row):
            for c in range(col):
                if grid[r][c] == "1":
                    num_islands += 1
                    grid[r][c] = "0"
                    neighbors = deque([(r, c)])
                    while neighbors:
                        i, j = neighbors.popleft()
                        for x, y in [(i - 1, j), (i + 1, j), (i, j - 1), (i, j + 1)]:
                            if 0 <= x < row and 0 <= y < col and grid[x][y] == "1":
                                neighbors.append((x, y))
                                grid[x][y] = "0"

        return num_islands

并查集

并查集算法不是很常用，但是思路很清晰，初始设每个陆地都是一个岛屿，比较两个相邻的岛屿是否为同一个岛屿，如果不是同一个岛屿则合并这两个岛屿，并将岛屿数量减1，最后剩余的岛屿数量就是本题的解。难点在于如何判断两个相邻岛屿为同一个岛屿，而且如何合并两个岛屿？每一个岛屿设定一个首都即可，如果两个岛屿的首都相同，则在同一个岛屿上，否则不在同一个岛屿，合并时直接选择某一个首都最为总首都即可实现岛屿合并。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
class UnionFind:
    def __init__(self, grid):
        m, n = len(grid), len(grid[0])
        self.count = 0
        self.parent = [-1] * (m * n)
        self.rank = [0] * (m * n)
        for i in range(m):
            for j in range(n):
                if grid[i][j] == "1":
                    self.parent[i * n + j] = i * n + j
                    self.count += 1

    def find(self, i):
        if self.parent[i] != i:
            self.parent[i] = self.find(self.parent[i])
        return self.parent[i]

    def union(self, x, y):
        rootx = self.find(x)
        rooty = self.find(y)
        if rootx != rooty:
            self.parent[rooty] = rootx
            self.count -= 1

    def getCount(self):
        return self.count


class Solution:
    def numIslands(self, grid):
        nr = len(grid)
        if nr == 0:
            return 0
        nc = len(grid[0])

        uf = UnionFind(grid)
        for r in range(nr):
            for c in range(nc):
                if grid[r][c] == "1":
                    grid[r][c] = "0"
                    for x, y in [(r - 1, c), (r + 1, c), (r, c - 1), (r, c + 1)]:
                        if 0 <= x < nr and 0 <= y < nc and grid[x][y] == "1":
                            uf.union(r * nc + c, x * nc + y)

        return uf.getCount()

刷题总结

  朋友圈问题是一类经典的面试问题，因此小伙伴们务必掌握基本的DFS和BFS算法，至于并查集问题，大家理解即可，因为并查集实现也没用DFS和BFS容易，而且时间复杂度也并没有提升，只需要小伙伴们能够说出并查集思路。

-------------本文结束感谢您的阅读-------------
0%